# 43/100 二叉树-验证二叉搜索树
# leetcode第98题: https://leetcode.cn/problems/validate-binary-search-tree/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/12
from leetcode.bds import TreeNode, TreeConverter
import leetcode.test as test
from typing import Optional


def isValidBST_rec(root: Optional[TreeNode]) -> bool:
    def in_order(cur: TreeNode):
        nonlocal min_val, res
        if cur:
            in_order(cur.left)
            if cur.val <= min_val:
                res = False and res
            else:
                min_val = cur.val
            in_order(cur.right)
        res = True and res

    res = True
    min_val = float('-inf')
    in_order(root)
    return res


def isValidBST_rec_opt(root: Optional[TreeNode]) -> bool:
    def in_order(cur: TreeNode) -> bool:
        nonlocal outer_val
        if not cur:
            return True
        if not in_order(cur.left):  # 遍历左子树
            return False
        if cur.val <= outer_val:  # 检查当前节点
            return False
        outer_val = cur.val
        return in_order(cur.right)  # 遍历右子树

    outer_val = float('-inf')
    return in_order(root)


def isValidBST_stack(root: Optional[TreeNode]) -> bool:
    stack, inorder = [], float('-inf')

    while stack or root:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        # 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
        if root.val <= inorder:
            return False
        inorder = root.val
        root = root.right

    return True


if __name__ == '__main__':
    t1 = TreeConverter.list_to_tree([2, 1, 3])
    t2 = TreeConverter.list_to_tree([5, 1, 4, None, None, 3, 6])
    t3 = TreeConverter.list_to_tree([2, 2, 2])
    inp = [{"root": t1}, {"root": t2}, {"root": t3}, ]
    out = [True, False, False]
    test.test_function(isValidBST_rec, inp, out, times=10000)
    test.test_function(isValidBST_rec_opt, inp, out, times=10000)
    test.test_function(isValidBST_stack, inp, out, times=10000)
